package com.wfm.niuke.duistackqueue;

import java.util.PriorityQueue;

/**
 * i-k+1的来由  比如k=3
 * 1  2  3  4  5  6  7  8  9
 *       |     |
 *    i-k+1    i
 */
public class BM45滑动窗口最大值239 {
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)-> o1[0]!=o2[0]?o2[0]-o1[0]:o2[1]-o1[1]);
        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{nums[i],i});
        }
        int[] ans = new int[n-k+1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; i++) {
            pq.offer(new int[]{nums[i],i});
            while (pq.peek()[1]<i-k+1){
                pq.poll();
            }
            ans[i-k+1]=pq.peek()[0];
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new BM45滑动窗口最大值239().new Solution();
    }
}